public class test6 {
    class Solution {
        public int minDistance(String word1, String word2) {
            //找最长公共子序列
            char[] ch1 = word1.toCharArray();
            char[] ch2 = word2.toCharArray();
            int[][] dp = new int[ch1.length+1][ch2.length+1];

            //初始化【必不可少！】
            for(int i = 0;i<ch1.length+1;i++){
                dp[i][0] = i;
            }
            for(int j = 0;j<ch2.length+1;j++){
                dp[0][j] = j;
            }

            for(int i = 1;i<ch1.length+1;i++){
                for(int j = 1;j<ch2.length+1;j++){
                    if(ch1[i-1]==ch2[j-1]){
                        //不用改变
                        dp[i][j] = dp[i-1][j-1];
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    }
                }
            }
            return dp[ch1.length][ch2.length];

        }
    }
}
